#
# @lc app=leetcode.cn id=15 lang=python3
#
# [15] 三数之和
#

# @lc code=start
class Solution:
    def find(self, nums, x, i, j):
        while i <= j:
            mid = (i+j) // 2
            if x < nums[mid]:
                j = mid-1
            elif x > nums[mid]:
                i = mid+1
            else:
                return True
        return False


    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        if (not nums or n < 3):
            return res
        nums.sort()
 
        if (nums[0] > 0 or nums[n-1] < 0):
            return res
        for i in range(n):
            
            l = i+1
            r = n-1
            if i != 0 and nums[i] == nums[i-1]:
                continue
            while(l < r):
                if nums[l]+nums[r]+nums[i] > 0:
                    r = r-1
                elif nums[l]+nums[r]+nums[i] < 0:
                    l = l+1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    while(l<r and nums[l]==nums[l+1]):
                        l = l+1
                    while(l<r and nums[r]==nums[r-1]):
                        r = r-1    
                    l = l+1
                    r = r-1

        return res
    
# @lc code=end

